\documentclass{sig-alternate}

\usepackage{times}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm} 
\usepackage{amsfonts}
\usepackage{color}
\usepackage{subfigure}
\usepackage{framed}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}{Corollary}

\newcommand{\eat}[1]{}

\newcommand{\PosInt}{\mathbb{Z}^+}
\newcommand{\NegInt}{\mathbb{Z}^-}
\newcommand{\NonNegInt}{\mathbb{Z}_0^+}
\newcommand{\NonPosInt}{\mathbb{Z}_0^-}
\newcommand{\PosRea}{\mathbb{R}^+}
\newcommand{\NegRea}{\mathbb{R}^-}
\newcommand{\NonNegRea}{\mathbb{R}_0^+}
\newcommand{\NonPosRea}{\mathbb{R}_0^-}

\newcommand{\andrew}[1]{\textcolor{red}{\\Andrew: #1\\}}
\newcommand{\atish}[1]{\textcolor{red}{\\Atish: #1\\}}
\newcommand{\debmalya}[1]{\textcolor{red}{\\Debmalya: #1\\}}
\newcommand{\gagan}[1]{\textcolor{red}{\\Gagan: #1\\}}

\newcommand{\diverse}{{\sc Diversifier }}
\newcommand{\opt}{\text{\sc opt}}
\newcommand{\off}{\text{\sc off}}
\newcommand{\yes}{{\sc Yes }}
\newcommand{\no}{{\sc No }}
\newcommand{\ex}{\mathbb{E}}

\conferenceinfo{WSDM}{'12 Seattle, Washington, USA}

\title{Online Selection of Diverse Results}
\numberofauthors{4}
\author{
	\alignauthor
	Debmalya Panigrahi\titlenote{Part of this work was done while the 
	author was an intern at Google Research, Mountain View, CA.}\\
	\affaddr{CSAIL, MIT}\\
	\affaddr{Cambridge, MA.}\\
	\email{debmalya@mit.edu}
	\alignauthor
	Atish Das Sarma\\
	\affaddr{Google Research}\\
	\affaddr{Mountain View, CA.}\\
	\email{dassarma@google.com}
	\alignauthor
	Gagan Aggarwal\\
	\affaddr{Google Research}\\
	\affaddr{Mountain View, CA.}\\
	\email{gagana@google.com}
	\and
	\alignauthor
	Andrew Tomkins\\
	\affaddr{Google Research}\\
	\affaddr{Mountain View, CA.}\\
	\email{tomkins@google.com}
}

\begin{document}

\maketitle

\begin{abstract}
	With the phenomenal growth in the volume of easily accessible 
	information via various web-based services, it 
	has become essential for service providers to provide users
	with representative summaries of such information.
	Further, online commercial services including social networking
	and micro-blogging websites, e-commerce portals, leisure and 
	entertainment websites, etc. recommend interesting content to users that
	is simultaneously diverse on many different axes such as topic, 
	geographic specificity, etc. The key algorithmic question in all 
	these applications is the 
	generation of succinct, representative,
	and relevant summaries from large streams of data coming from
	a variety of sources. In this paper, we formally model this 
	optimization problem,
	identify its key structural characteristics, and use these 
	observations to design an extremely scalable and efficient algorithm. 
	We analyze the algorithm using theoretical 
	techniques to show that it always produces a nearly optimal solution, 
	and also perform wide-scale experiments on both real-world and synthetically
	generated  datasets, which confirm that our algorithm performs even better than
	its analytical guarantees in practice, and also outperforms other natural 
	algorithms for the problem by a wide margin.
\end{abstract}

\input introduction

\input functions 

\input problem

\input algorithm

\input experiments

\input related

\input discussions

\bibliographystyle{plain}
\bibliography{ref}

\appendix

\input appendix

\end{document}
